#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    """
    @param: A: An integer array
    @param: target: An integer
    @return: An integer
    """
    def MinAdjustmentCost(self, A, target):
        # assert target >= 0
        # all([ele >= 0 for ele in A])

        self.max = max(A)
        self.rows = len(A) + 1          # 多了第0行, 用来作为边界
        self.cols = self.max + 1        # 多了一列, 表示取值为0
        self.A = A
        self.target = target

        self.dp_mat = self.make_matrix(self.rows, self.cols, 0)

        self.drive_dp()
        return min(self.dp_mat[self.rows-1])

    def drive_dp(self):
        for row, ele in enumerate(self.A, 1):
            for candidate_n in range(self.cols):
                # A中的ele取值candidate_n
                if row == 1:
                    all_adjust_step = self.dp_mat[row][candidate_n] = abs(ele - candidate_n)
                else:
                    all_adjust_step = self.ele_2_cand_min_step(row, ele, candidate_n)
                self.dp_mat[row][candidate_n] = all_adjust_step

    def ele_2_cand_min_step(self, row, ele, candidate_n):
        current_steps = abs(ele - candidate_n)

        begin = max(0, candidate_n - self.target)
        end   = min(self.max, candidate_n + self.target)
        last_valid_steps = self.dp_mat[row-1][begin : end+1]
        last_min_steps = min(last_valid_steps)

        return current_steps + last_min_steps

    def make_matrix(self, rows, cols, init_v=None):
        one_row = [init_v] * cols
        matrix = [list(one_row) for i in range(rows)]
        return matrix


def main():
    print("start main")
    l = [1,4,2,3]
    s = Solution()
    ret = s.MinAdjustmentCost(l, 1)
    print(ret)

if __name__ == "__main__":
    main()
